/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/surrounded-regions
   @Language: C++
   @Datetime: 16-02-09 08:39
   */

class Solution {
	void vist(vector<vector<char> > &board,int i,int j){
		if (i<0 || i>=board.size() || j<0 || j>=board[0].size()
				|| board[i][j]!='O')
			return;
		board[i][j]='*';
		vist(board,i-1,j);
		vist(board,i+1,j);
		vist(board,i,j-1);
		vist(board,i,j+1);
	}

public:
	/**
	 * @param board a 2D board containing 'X' and 'O'
	 * @return void
	 * Tip: traversal 4 margins, if element is 'O',
	 *      set it as '*', DFS traversal this element's neighbors,
	 */
	void surroundedRegions(vector<vector<char> > &board) {
		// Write your code here
		if (board.size()<1 || board[0].size()<1) return;
		int M=board.size(), N=board[0].size();

		for(int i=0; i<N; ++i){
			if (board[0][i]=='O') vist(board,0,i);
			if (board[M-1][i]=='O') vist(board,M-1,i);
		}
		for(int i=0; i<M; ++i){
			if (board[i][0]=='O') vist(board,i,0);
			if (board[i][N-1]=='O') vist(board,i,N-1);
		}
		for(int i=0; i<M; ++i)
			for(int j=0; j<N; ++j)
				board[i][j]=(board[i][j]=='*' ? 'O' : 'X');
	}
};
